package special;

import java.util.Arrays;
import java.util.TreeSet;

public class LeeCode_LCP_75_Failed {
    public static void main(String[] args) {
        System.out.println(challengeOfTheKeeper(new String[]{".#..", "..##", ".#S.", ".#.T"}));
        System.out.println(challengeOfTheKeeper(new String[]{"S###.", "..###", "#..##", "##..#", "###.T"}));
        System.out.println(challengeOfTheKeeper(new String[]{".....","##S..","...#.","T.#..","###.."}));
    }

    private static int challengeOfTheKeeper(String[] maze) {
        int n = maze.length;
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], 10000);
        }
        int ei = 0, ej = 0, si = 0, sj = 0;
        for (int i = 0; i < n; i++) {
            boolean flag1 = false, flag2 = false;
            for (int j = 0; j < n; j++) {
                char now = maze[i].charAt(j);
                if (now == 'T') {
                    dp[i][j] = 0;
                    ei = i;
                    ej = j;
                    flag1 = true;
                } else if (now == 'S') {
                    si = i;
                    sj = j;
                    flag2 = true;
                }
            }
            if (flag1 && flag2) {
                break;
            }
        }
        dfs(dp, ei, ej, maze, new boolean[n][n]);
        int[] loc = new int[]{si, sj};
        if ( dp[si][sj] == 10000){
            return -1;
        }
        TreeSet<Integer> ans = new TreeSet<>();
        dfsMove(loc, -1, -1, 0, ans, dp, maze);
        return ans.first() == 10000 ? -1 : ans.first();
    }
    private static void dfsMove(int[] loc, int fai, int faj, int max, TreeSet<Integer> ans, int[][] dp, String[] maze){
        int i = loc[0], j = loc[1];
        int n = maze.length;
        if (maze[i].charAt(j) == 'T'){
            ans.add(max);
            return;
        }
        int min = 10000;
        if (i - 1 >= 0 && (i - 1 != fai || j != faj)){
            min = Math.min(dp[i - 1][j], min);
        }
        if (i + 1 < n && (i + 1 != fai || j != faj)){
            min = Math.min(dp[i + 1][j], min);
        }
        if (j - 1 >= 0 && (i != fai || j - 1 != faj)){
            min = Math.min(dp[i][j - 1], min);
        }
        if (j + 1 < n && (i != fai || j + 1 != faj)){
            min = Math.min(dp[i][j + 1], min);
        }

        int tm = max;
        if (maze[i].charAt(j) != 'S'){
            int ti = n - i - 1;
            int tj = n - j - 1;
            int tmi = dp[ti][j];
            if (tmi == 10000){
                if (maze[ti].charAt(j) != '#'){
                    tm = 10000;
                }
            }else {
                tm = Math.max(tm, tmi);
            }
            int tmj = dp[i][tj];
            if (tmj == 10000){
                if (maze[i].charAt(tj) != '#'){
                    tm = 10000;
                }
            }else {
                tm = Math.max(tm, tmj);
            }
        }

        if (tm == 10000){
            ans.add(10000);
            return;
        }
        if (i - 1 >= 0 && (i - 1 != fai || j != faj) && dp[i - 1][j] == min){
            dfsMove(new int[]{i - 1, j}, i, j, tm, ans, dp, maze);
        }
        if (j - 1 >= 0 && (i != fai || j - 1 != faj) && dp[i][j - 1] == min){
            dfsMove(new int[]{i, j - 1}, i, j, tm, ans, dp, maze);
        }
        if (i + 1 < n && (i + 1 != fai || j != faj) && dp[i + 1][j] == min){
            dfsMove(new int[]{i + 1, j}, i, j, tm, ans, dp, maze);
        }
        if (j + 1 < n && (i != fai || j + 1 != faj) && dp[i][j + 1] == min){
            dfsMove(new int[]{i, j + 1}, i, j, tm, ans, dp, maze);
        }
    }

    private static void move(int[] loc, int[][] dp, String[] maze) {
        int i = loc[0], j = loc[1];
        int min = getMin(dp, maze, i, j);
        if (i - 1 >= 0 && min == dp[i - 1][j]) {
            loc[0] = i - 1;
        } else if (i + 1 < maze.length && min == dp[i + 1][j]) {
            loc[0] = i + 1;
        } else if (j - 1 >= 0 && min == dp[i][j - 1]) {
            loc[1] = j - 1;
        } else if (j + 1 < maze.length && min == dp[i][j + 1]) {
            loc[1] = j + 1;
        }
    }

    private static int getMin(int[][] dp, String[] maze, int i, int j) {
        int d1 = 10000, d2 = 10000, d3 = 10000, d4 = 10000;
        if (i + 1 < maze.length && maze[i + 1].charAt(j) != '#') {
            d1 = dp[i + 1][j];
        }
        if (j + 1 < maze.length && maze[i].charAt(j + 1) != '#') {
            d2 = dp[i][j + 1];
        }
        if (i - 1 >= 0 && maze[i - 1].charAt(j) != '#') {
            d3 = dp[i - 1][j];
        }
        if (j - 1 >= 0 && maze[i].charAt(j - 1) != '#') {
            d4 = dp[i][j - 1];
        }
        return Math.min(d1, Math.min(d2, Math.min(d3, d4)));
    }

    private static void dfs(int[][] dp, int i, int j, String[] maze, boolean[][] used) {
        if (used[i][j])
            return;
        if (maze[i].charAt(j) == '#') {
            used[i][j] = true;
            return;
        }
        int min = getMin(dp, maze, i, j);
        dp[i][j] = Math.min(dp[i][j], min + 1);
        used[i][j] = true;
        if (i + 1 < maze.length) {
            dfs(dp, i + 1, j, maze, used);
        }
        if (j + 1 < maze.length) {
            dfs(dp, i, j + 1, maze, used);
        }
        if (i - 1 >= 0) {
            dfs(dp, i - 1, j, maze, used);
        }
        if (j - 1 >= 0) {
            dfs(dp, i, j - 1, maze, used);
        }
    }
}
